package com.zy.algorithm.sort;

import java.util.List;

/**
 * @author ZhaoYi
 * @date 2023/11/13 14:49
 * 冒泡
 * 思想：通过不断比较相邻的元素并交换位置，使最大（或最小）的元素逐渐浮到数组的末端。
 * 特点：时间复杂度为O(n^2)，稳定性好(相等不交换)，但是相对较慢。
 */
public class BubblingSort<T extends Comparable<? super T>> implements ISort<T> {


    @Override
    public List<T> sort(List<T> list) {

        if (list == null || list.size() <= 1) {
            return list;
        }

        //1, 2, 3, 4, 5

        int completeIndex = list.size(); //9


        while (completeIndex > 0) {

            //System.out.println("completeIndex is " + completeIndex);
            boolean isSorted = true;
            for (int i = 0; i < (completeIndex - 1); i++) {
                T before = list.get(i);
                T after = list.get(i + 1);
                if (before.compareTo(after) > 0) {
                    list.set(i, after);
                    list.set(i + 1, before);
                    isSorted = false;
                }

            }

            if (isSorted) {
                System.out.println("本轮已发现全部有序直接退出");
                return list;
            }

            completeIndex--;

        }


        return list;
    }
}
